package com.xy6.struct.stack;


/**
 * 栈
 * <p>基于数组实现
 * 
 * @author zhang
 * @since 2017-09-03
 */
public class Stack<T> {

	private static final int DEFAULT_SIZE = 16; 
	
	private Object[] elems;
	
	private int size = 0;
	
	private int capacity = 0;
	
	public Stack(){
		capacity = DEFAULT_SIZE;
		elems = new Object[capacity];
	}
	
	/**
	 * 入栈
	 * 
	 * @param elem
	 */
	public void push(T elem){
		updateCapacity();
		elems[size] = elem;
		size++;
	}
	
	/**
	 * 出栈
	 * 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T pop(){
		Object elem = elems[size - 1];
		elems[size-1] = null;
		size--;
		return (T) elem;
	}
	
	/**
	 * 集合元素个数
	 * 
	 * @return
	 */
	public int size(){
		return size;
	}
	
	/**
	 * 更新集合长度
	 * <p>如果集合将满，则扩展集合长度
	 * TODO <p>如果集合空置率很高，则收缩集合
	 */
	private void updateCapacity(){
		if(size < capacity){
			return;
		}
		capacity = capacity << 1 + 1;
		expand();
	}
	
	/**
	 * 扩展集合长度
	 * <p>将集合拷贝到一个新的集合中
	 */
	private void expand(){
		Object[] newelems = new Object[capacity];
		for(int i=0; i<size; i++){
			newelems[i] = elems[i];
		}
		elems = newelems;
	}
	
}
